package org.ranki.moerae.lachesis;

import org.ranki.moerae.clotho.context.Context;
import org.ranki.moerae.clotho.node.AbstractNode;

import java.util.*;

public class Greedy implements Search{
    private volatile static Greedy greedy;
    private Greedy (){}
    public static Greedy getGreedy() {
        if (greedy == null) {
            synchronized (Greedy.class) {
                if (greedy == null) {
                    greedy = new Greedy();
                }
            }
        }
        return greedy;
    }
    @Override
    public void search(AbstractNode start, AbstractNode end, Context context) {
        List<AbstractNode> path=new ArrayList<AbstractNode>();
        find(path,new HashSet<AbstractNode>(),start,end);
        context.getParams().put("path",path);
    }
    private boolean find(List<AbstractNode> res, Set<AbstractNode> seen, AbstractNode curr, AbstractNode end){
        seen.add(curr);
        res.add(curr);
        if(curr==end){
            return true;
        }
        Queue<AbstractNode> queue=new PriorityQueue<>(
                (a,b)->(a.getAveCostTime()-b.getAveCostTime())
        );
        for(AbstractNode next: curr.getNexts()){
            queue.offer(next);
        }
        while (!queue.isEmpty()){
            AbstractNode next= queue.poll();
            if(seen.contains(next)){
                return false;
            }
            if(find(res,seen,next,end)){
                return true;
            }
        }
        seen.remove(curr);
        res.remove(res.size()-1);
        return false;
    }
}
